package test.algorithm.dfs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class DFSTest_20130121 {
	
	private static int MAX_LENGTH;
	public static Integer[] visited; // 0: not visited, 1: visited
	private static Integer[][] graph;
	private static Integer start;
	
	private static Integer[][] test;
	private static Integer cnt = 0;
	private static Map<Integer, Integer[]> map;
	private static int idx; // 순서대로 지나갔는지 체크
	private static int idx2;
//	private static int current;
	private static Map<Integer, Integer> maptest;
	
	private static List<Integer> path = new ArrayList<Integer>();
	
	public static void main(String args[]) {
		
		start = 1;
		
		idx = 1;
		idx2 = 0;
		
		/*test = new Integer[][] {
				{0, 0},
				{0, 2},
				{2, 2},
		};
		Map<Integer, Integer[]> map1 = new HashMap<Integer, Integer[]>();
		Integer[] i;
		i= new Integer[]{0, 0};
		map1.put(1, i);
		
		i= new Integer[]{0, 2};
		map1.put(7, i);
		
		i= new Integer[]{2, 2};
		map1.put(9, i);*/
		
		maptest = new HashMap<Integer, Integer>();
		maptest.put(1, 1);
		maptest.put(7, 2);
		maptest.put(3, 3);
//		map2.put(0, 0);
//		map1.put(1, map2);
//		map2.put(0, 2);
//		map2.put(2, 2);
		
		
		initGraph3X3();
//		initGraph6X6();
		
		findPath(start);
		
		
		System.out.println("PATH : " + Arrays.asList(path.toArray()));
	}
	
	public static void findPath(int start) {
		if (start > graph.length) {
			System.out.println("Please input valid start point less then " + graph.length);
			return;
		}
		dfs(start, (start-1));
//		System.out.print("Finish!");
	}
	
	private static void dfs(int current, int v) {
		
		System.out.println("# CURRENT : " + current);
		System.out.println("# IDX : " + idx);
		System.out.println("# IDX2 : " + idx2);
		System.out.println(Arrays.toString(visited));
		
		// Last Move
		if (idx2 == 8) {
			
		}
		
		// moveable path validation
		boolean isMoveable = false;
		for (int i=0; i<MAX_LENGTH; i++) {
			if (graph[current][i] == 1 && visited[i] != 1) {
				isMoveable = true;
				break;
			}
		}
		/*for (int i=0; i<MAX_LENGTH; i++) {
			if (graph[v][i] == 1 && visited[i] != 1) {
				isMoveable = true;
				break;
			}
		}*/
		
		/*
		 * (v+1) : 현재위치, (i+1) : 이동할 위치
		 */
//		Integer[] width_height = map.get(v+1);
//		if (maptest.get(v+1) == null) {
//			isMoveable = true;
//		}
		if (maptest.get(v+1) != null && maptest.get(v+1) > idx) {
			isMoveable = false;
		} else if (maptest.get(v+1) != null && maptest.get(v+1) == idx) {
			isMoveable = true;
			idx++;
		}
		
		
		
		if (!isMoveable) {
//			visited[v] = 1;
			return;
		}
		
		// Path Validation
//		for (int k=0; k<test.length; k++) {
//			
//		}
		
		
		
		visited[v] = 1;
//		System.out.print((v+1) + ">");
		path.add(v+1);
		
		for (int i=0; i<MAX_LENGTH; i++) {
			if (graph[v][i] == 1 && visited[i] == 0) {
				
				/*if (maptest.get(v+1) != null && maptest.get(v+1) > idx) {
					isMoveable = false;
				} else if (maptest.get(v+1) != null && maptest.get(v+1) == idx) {
					isMoveable = true;
					idx++;
				}
				if (!isMoveable) {
//					visited[v] = 1;
//					return;
					break;
				}*/
//				current = v+1;
				idx2++;
				dfs(v, i);
			}
		}
	}
	
	public static void initGraph3X3() {
		/*
		 * 123
		 * 456
		 * 789
		 */
		graph = new Integer[][] {
				 {0,1,0,1,0,0,0,0,0},
				 {1,0,1,0,1,0,0,0,0},
				 {0,1,0,0,0,1,0,0,0},
				 {1,0,0,0,1,0,1,0,0},
				 {0,1,0,1,0,1,0,1,0},
				 {0,0,1,0,1,0,0,0,1},
				 {0,0,0,1,0,0,0,1,0},
				 {0,0,0,0,1,0,1,0,1},
				 {0,0,0,0,0,1,0,1,0}};
		
		MAX_LENGTH = graph.length;
		visited = new Integer[MAX_LENGTH];
		for (int i=0; i<visited.length; i++) {
			visited[i] = 0;
		}
	}
	
	public static void initGraph6X6() {
		
		graph = new Integer[][]{
				{0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0}};
		
		MAX_LENGTH = graph.length;
		visited = new Integer[MAX_LENGTH];
		for (int i=0; i<visited.length; i++) {
			visited[i] = 0;
		}
	}
	
	public static void initGraph2() {
		graph = new Integer[][]{
				 {0,1,1,1,0,0,0,0,0,0},
				 {1,0,0,0,1,1,0,0,0,0},
				 {1,0,0,0,0,1,0,0,0,0},
				 {1,0,0,0,0,1,1,0,0,0},
				 {0,1,0,0,0,0,0,1,0,0},
				 {0,1,1,1,0,0,0,1,1,1},
				 {0,0,0,1,0,0,0,0,0,1},
				 {0,0,0,0,1,1,0,0,1,0},
				 {0,0,0,0,0,1,0,1,0,1},
				 {0,0,0,0,0,1,1,0,1,0}
		};
	}
}
